﻿using System;
using System.Collections.Generic;

namespace Assets.Scripts.Algrithm
{
    public class MaxHeap<T> where T : IComparable<T>
    {
        private readonly List<T> _heap;

        public MaxHeap()
        {
            _heap = new List<T>();
        }

        public void Insert(T item)
        {
            //加入末尾
            _heap.Add(item);
            int currentIndex = _heap.Count - 1;
            while (currentIndex > 0)
            {
                int parentIndex = (currentIndex - 1) / 2;
                if (_heap[parentIndex].CompareTo(_heap[currentIndex]) < 0)
                {
                    Swap(currentIndex, parentIndex);
                    currentIndex = parentIndex;
                }
                else
                {
                    //已经在正确的位置了
                    break;
                }
            }
        }

        public T ExtractMax()
        {
            if (_heap.Count == 0) throw new InvalidOperationException("Heap is empty");
            T max = _heap[0];
            _heap[0] = _heap[_heap.Count - 1];
            _heap.RemoveAt(_heap.Count - 1);
            //从根节点开始调整堆使其有序
            MaxHeapify(0);
            //返回根节点
            return max;
        }

        //从 index 位置向下（列表中向后）调整堆到有序
        private void MaxHeapify(int index)
        {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            //假设当前节点就是最大节点
            int largest = index;
            if (leftChildIndex < _heap.Count && _heap[leftChildIndex].CompareTo(_heap[largest]) > 0)
            {
                largest = leftChildIndex;
            }

            if (rightChildIndex < _heap.Count && _heap[rightChildIndex].CompareTo(_heap[largest]) > 0)
            {
                largest = rightChildIndex;
            }

            if (largest != index)
            {
                Swap(largest, index);
                MaxHeapify(largest);
            }
        }

        private void Swap(int i, int j) => (_heap[i], _heap[j]) = (_heap[j], _heap[i]); // 元组解构用于
    }
}